Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Leaf Processing Pattern (medium)
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Tree View Pattern (medium)
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Comparison of Two Trees Pattern (medium)
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Serialize and Deserialize Tree Pattern (hard)
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Verify Preorder Serialization of a Binary Tree

Problem Statement

You are given a string called preorder that represents the serialization of a binary tree.

This serialization string is created using a preorder traversal, where each node's value is recorded if it is a non-null node. Otherwise, we record using a sentinel value such as '#'.

The string preorder contains only integers and the character '#', separated by commas. The format is always valid, so there will be no cases like two consecutive commas (e.g., "1,,4").

Return true, if this string is a valid serialization of a binary tree. Otherwise, return false.

Note: Note: You are not allowed to reconstruct the tree.

Examples

  1. Example 1:
    • Input: "5,2,#,#,3,1,#,#,#"
    • Expected Output: true
    • Justification: The preorder traversal "5,2,#,#,3,1,#,#,#" represents a valid binary tree. It can be visualized as:
    5
   /
  2
   \
    3
    /
   1
  1. Example 2:
    • Input: "7,3,1,#,#,4,#,#,8,#,2,#,#"
    • Expected Output: true
    • Justification: The serialization "7,3,1,#,#,4,#,#,8,#,2,#,#" corresponds to a valid binary tree:
    7
   / \
  3   1
     /
    4
     \
      8
       \
        2
  1. Example 3:
    • Input: "1,#,#,2"
    • Expected Output: false
    • Justification: The serialization "1,#,#,2" cannot represent a valid binary tree. After the node 1 and its two null children, there should not be any additional nodes left, but 2 appears, which violates the preorder traversal structure.

Solution

To solve this problem, we start by recognizing that every non-null node in a binary tree requires a slot and provides two additional slots for its children. Meanwhile, a null node ('#') occupies a slot without adding any new slots. We initialize our available slots to 1 for the root node. As we traverse through the preorder string, each comma indicates the end of a node description. We decrement the available slots by one for every node processed. If the processed node is non-null, we add two more slots (since it provides room for two children); if it's null, we simply continue. The algorithm checks whether all slots are used up correctly by the end of the string.

The approach is efficient because it ensures a linear traversal through the input, checking at each step whether any inconsistencies exist in the structure of the binary tree. By the end of the string, if the slots available are exactly zero, then the preorder string is a valid serialization of a binary tree. Otherwise, it is not. This method allows us to validate the input without reconstructing the tree, keeping the solution optimal in both time and space complexity.

Step-by-Step Algorithm

  1. Initialize a variable availableSlots to 1. This represents the initial slot required for the root node.
  2. Calculate the length of the input string preorder and store it in the variable length.
  3. Loop through each character in the preorder string from the first to the second last character:
    • Check if the current character is a comma (,):
      • If true, decrement availableSlots by 1, since processing a node consumes one slot.
      • Check if availableSlots is less than 0:
        • If true, return false immediately since there are not enough slots for the upcoming nodes.
      • If the previous character is not '#', increment availableSlots by 2, indicating that a non-null node was processed, which creates two more slots for its children.
  4. Process the last node:
    • If the last character of preorder is '#', decrement availableSlots by 1 since it consumes one slot.
    • If the last character is not '#', increment availableSlots by 1. Here, the last non-null node adds 2 slots and consumes 1 slot. So, we are adding remaining 1 slot only.
  5. Check the final count of availableSlots:
    • If availableSlots is 0, return true, indicating a valid serialization.
    • Otherwise, return false.

Algorithm Walkthrough

Let's walk through the input "5,2,#,#,3,1,#,#,#" step-by-step:

  1. Initialize availableSlots = 1.
  2. Calculate length = 17 (length of the input string).
  3. Start loop with i = 0 to i = 16 (excluding the last character for separate processing):
    • i = 0: preorder.charAt(0) = '5', not a comma, continue to the next character.
    • i = 1: preorder.charAt(1) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 0.
      • Check the previous character preorder.charAt(0) = '5', which is not '#'.
      • Increment availableSlots by 2: availableSlots = 2.
    • i = 2: preorder.charAt(2) = '2', not a comma, continue to the next character.
    • i = 3: preorder.charAt(3) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 1.
      • Check the previous character preorder.charAt(2) = '2', which is not '#'.
      • Increment availableSlots by 2: availableSlots = 3.
    • i = 4: preorder.charAt(4) = '#', not a comma, continue to the next character.
    • i = 5: preorder.charAt(5) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 2.
      • Check the previous character preorder.charAt(4) = '#', which is '#', no new slots created.
    • i = 6: preorder.charAt(6) = '#', not a comma, continue to the next character.
    • i = 7: preorder.charAt(7) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 1.
      • Check the previous character preorder.charAt(6) = '#', which is '#', no new slots created.
    • i = 8: preorder.charAt(8) = '3', not a comma, continue to the next character.
    • i = 9: preorder.charAt(9) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 0.
      • Check the previous character preorder.charAt(8) = '3', which is not '#'.
      • Increment availableSlots by 2: availableSlots = 2.
    • i = 10: preorder.charAt(10) = '1', not a comma, continue to the next character.
    • i = 11: preorder.charAt(11) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 1.
      • Check the previous character preorder.charAt(10) = '1', which is not '#'.
      • Increment availableSlots by 2: availableSlots = 3.
    • i = 12: preorder.charAt(12) = '#', not a comma, continue to the next character.
    • i = 13: preorder.charAt(13) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 2.
      • Check the previous character preorder.charAt(12) = '#', which is '#', no new slots created.
    • i = 14: preorder.charAt(14) = '#', not a comma, continue to the next character.
    • i = 15: preorder.charAt(15) = ',', a comma is found.
      • Decrement availableSlots by 1: availableSlots = 1.
      • Check the previous character preorder.charAt(14) = '#', which is '#', no new slots created.
  4. Process the last node:
    • preorder.charAt(16) = '#', decrement availableSlots by 1: availableSlots = 0.
  5. Check final slot count: availableSlots is 0, so return true.

By following this step-by-step process, we verify that the serialization "5,2,#,#,3,1,#,#,#" is valid.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • The algorithm iterates over each character in the input string exactly once. Therefore, the time complexity is , where n is the length of the input string.

Space Complexity

  • The space complexity is since the algorithm only uses a fixed amount of extra space (i.e., a few variables like availableSlots and length) regardless of the size of the input string.
Verify Preorder Serialization of a Binary Tree (medium)
Create Binary Tree From Descriptions (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity